package 笔试2.美团.four;

import org.junit.Test;

import java.util.Arrays;

import static MyUtils.MHUtils.*;

//--哈夫曼树 拆左右各一边，让最大值最小值总和最小，有拆的次数限制
public class Main2 {

    private int back(int[] p, int tS) {
        can("p:"+Arrays.toString(p)+","+"tS:"+tS);
        if(tS==0){
            r(""+dajianxiao(p));
            return dajianxiao(p);
        }

        int min=99999;
        for (int i = 0; i < p.length-1; i++) {
            int[] a = shuangbiqieshuzu(0,i);
            int[] b = shuangbiqieshuzu(i+1,p.length-1);

            int s=0;
            if(a.length==1){
                s+=0;
            }else if(a.length>1){
                s+=back(a,tS-1);
            }

            if(b.length==1){
                s+=0;
            }else if(b.length>1){
                s+=back(b,tS-1);
            }
            min=Math.min(s,min);
        }

        r(min+";");
        return min;
    }

    int[] p ={5,1,2};

    @Test
    public void test() {
        int tS=2;
        int res = back(p,tS-1);
        System.out.println(res);
    }

    private int[] shuangbiqieshuzu(int s, int e) {
        int[] t = new int[0];
        if(s>e){
            return t;
        }

        int[] newp=new int[e-s+1];
        int f=0;
        for (int i =s; i <=e; i++) {
            newp[f]=p[i];
            f++;
        }
        return newp;
    }

    int dajianxiao(int[] p){
        if(p.length==1)return 0;
        Arrays.sort(p);
        return p[p.length-1]-p[0];
    }

}
